package primary.primary0;

/**
 * 这种问一共有多少种情况的，
 * 如果要具体情况 -> 回溯
 * 不要具体情况，只要数量 -> 递推
 * 这题递推，就看递推式是啥了，递推式应该是从起点到当前点有多少种走法。如果中间有些点不能走，那也是可行的。
 */
public class S0062不同路径 {
    /**
     * 动态规划，100
     */
    class Solution2 {
        public int uniquePaths(int m, int n) {
            int[][] record = new int[m][n];

            for(int i = 0; i < m; i++){
                for(int j = 0; j < n; j++){
                    if(i == 0 && j == 0){
                        record[0][0] = 1;
                        continue;
                    }
                    record[i][j] = getValue(record, i - 1, j) + getValue(record, i, j - 1);
                    //System.out.println(record[i][j]);
                }
            }
            return record[m - 1][n - 1];
        }

        private int getValue(int[][] record, int i, int j){
            if(i < 0 || i >= record.length || j < 0 || j >= record[0].length){
                return 0;
            }
            return record[i][j];
        }



    }

    /**
     * 逐个去找的话会超时，一个点会跑很多遍
     */
    class Solution {
        public int uniquePaths(int m, int n) {
            totalCount = 0;
            handleCurLoc(m, n, 0, 0);
            return totalCount;
        }

        private int totalCount;

        private void handleCurLoc(int totalRow, int totalCol, int row, int col){
            if(row == totalRow - 1 && col == totalCol - 1){
                // 存储当前路径，这里不需要存储，所以直接总和++
                totalCount ++;
                return;
            }
            if(row < 0 || row >= totalRow || col < 0 || col >= totalCol){
                return;
            }
            handleCurLoc(totalRow, totalCol, row + 1, col);
            handleCurLoc(totalRow, totalCol, row, col + 1);
        }
    }

    public static void main(String[] args) {
        int m = 1;
        int n = 2;
        int[][] record = new int[m][n];
    }
}
